package me.mingshan.algorithm.search;

/**
 * 二分搜索
 *
 * @author mingshan
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] source = {1, 3, 4, 5, 7, 9};
        //  System.out.println(search(source, 90, 0, source.length - 1));

        System.out.println(binarySearch(source, 5));
        System.out.println(binarySearch(source, 6));
        System.out.println(binarySearch3(source, 5));
        System.out.println(binarySearch3(source, 6));
    }

    /**
     * 左闭右开 [left, right)
     * 特点
     * 初始区间：left = 0, right = nums.length
     * <p>
     * 终止条件：while (left < right)
     * <p>
     * 更新逻辑：
     * <p>
     * nums[mid] < target → left = mid + 1
     * <p>
     * nums[mid] >= target → right = mid
     *
     * @param nums
     * @param target
     * @return
     */

    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        // 定义区间，右开
        int right = nums.length;
        while (left < right) {
            // 等同于 (left + right) / 2，防止溢出
            int mid = left + (right - left) / 2;

            // 如果目标值大于中间值，说明在右边
            if (nums[mid] < target) {
                // 左开
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 如果目标值大于中间值，说明在左边
                // 右闭
                right = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 左闭右闭 [left, right]
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearch3(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;    // 定义了target在左闭右闭的区间内，[left, right]
        while (left <= right) {
            //当left == right时，区间[left, right]仍然有效
            int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
            if (nums[middle] > target) {
                //target在左区间，所以[left, middle - 1]
                // 右闭
                right = middle - 1;
            } else if (nums[middle] < target) {
                //target在右区间，所以[middle + 1, right]
                // 左闭
                left = middle + 1;
            } else {
                //既不在左边，也不在右边，那就是找到答案了
                return middle;
            }
        }
        //没有找到目标值
        return -1;
    }

}
